// source.cpp : Defines the entry point for the application.
//

#include "stdafx.h"
#include "source.h"
#include<time.h>
#define N INT_MAX
#define MAX_LOADSTRING 100
#define IDC_MAIN_BUTTON	101
#define IDC_MAIN_EDIT 201// Button identifier
		// Edit box identifier

HWND hEdit,hWnd1,hWndDlg;
// Global Variables:
LARGE_INTEGER t1tango,t2tango,t1binar,t2binar;//ticks
LARGE_INTEGER frequencytango,frequencybinar; //ticks per second
double elapsedtimetango, elapsedtimebinar;
double PCFreq;
HINSTANCE hInstStatic;
HINSTANCE hInst;
char buffer[256],string[1000],string1[1000],buffer1[256];
int j;
int h;
int vec[1000];
int nr_nod;
int v[100000];
int ok[100000];
int l;
char s[10000][1000];
char cuv[1000][1000];
int val;
__int64 CounterStart=0;


HWND hWndHeadline;// current instance
TCHAR szTitle[MAX_LOADSTRING];					// The title bar text
TCHAR szWindowClass[MAX_LOADSTRING];			// the main window class name

ATOM				MyRegisterClass(HINSTANCE hInstance);
BOOL				InitInstance(HINSTANCE, int);
LRESULT CALLBACK	WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK	About(HWND, UINT, WPARAM, LPARAM);

//=====================================================================

typedef struct treeNode
{
	int value;
	treeNode *left, *right;
	treeNode *parent;
	int ales; //1-vizitat
	char color;
	treeNode *r,*l;
	treeNode *p;
}treeNode;
treeNode *root, *rootinit;
struct treeNode *grandparent(treeNode *n)
{
	if((n!=NULL) && (n->p!=NULL))
		return n->p->p;
	else
		return NULL;
}
struct treeNode *uncle(treeNode *n)
{
	treeNode *g=grandparent(n);
	if(g==NULL)
		return NULL;//daca nu exista bunic nu exista nici unchi
	if(n->p==g->l)
		return g->r;
	else
		return g->l;
}

treeNode ***mat;
void insert_case1(treeNode *&root_rb,treeNode *n);
void insert_case2(treeNode *&root_rb,treeNode *n);
void insert_case3(treeNode *&root_rb,treeNode *n);
void insert_case4(treeNode *&root_rb,treeNode*n);
void insert_case5(treeNode *&root_rb,treeNode *n);
int height(treeNode *subroot);
void sortare(int *ok, int n);
treeNode *creare_nod(int i, int j, int *v,treeNode *parent);
void repetare_el(int *v, int *ok, int n, int &l);
int arbore_complet(treeNode *subroot, int h, int n);
void randomelemente();
void calepreferata(treeNode *subroot, treeNode **pref, int &i);
void matrice_preordine(treeNode *subroot, treeNode ***mat, treeNode **pref, int &j, int *vec);
void linie(treeNode ***mat, int *vec, int j, treeNode **roots);
void rbInsert(treeNode *&subroot, treeNode *z);
void rightRotate( treeNode *&subroot, treeNode *y);
void leftRotate(treeNode *&subroot,treeNode *x);

void TANGO_TREE(treeNode **roots, int j, treeNode ***mat);
int cautare(int val);
int cautare2(int val);
//=====================================================================

void StartCounter()
{
    LARGE_INTEGER li;
    if(!QueryPerformanceFrequency(&li));
    PCFreq = double(li.QuadPart)/1000000000.0;

    QueryPerformanceCounter(&li);
    CounterStart = li.QuadPart;
}
double GetCounter()
{
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return double(li.QuadPart-CounterStart)/PCFreq;
}
int APIENTRY _tWinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPTSTR    lpCmdLine,
                     int       nCmdShow)
{
	UNREFERENCED_PARAMETER(hPrevInstance);
	UNREFERENCED_PARAMETER(lpCmdLine);

 	// TODO: Place code here.
	MSG msg;
	HACCEL hAccelTable;

	// Initialize global strings
	LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, IDC_SOURCE, szWindowClass, MAX_LOADSTRING);
	MyRegisterClass(hInstance);

	// Perform application initialization:
	if (!InitInstance (hInstance, nCmdShow))
	{
		return FALSE;
	}

	hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_SOURCE));

	// Main message loop:
	while (GetMessage(&msg, NULL, 0, 0))
	{
		if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
		{
			TranslateMessage(&msg);
			DispatchMessage(&msg);
		}
	}

	return (int) msg.wParam;
}

ATOM MyRegisterClass(HINSTANCE hInstance)
{
	WNDCLASSEX wcex;

	wcex.cbSize = sizeof(WNDCLASSEX);

	wcex.style			= CS_HREDRAW | CS_VREDRAW;
	wcex.lpfnWndProc	= WndProc;
	wcex.cbClsExtra		= 0;
	wcex.cbWndExtra		= 0;
	wcex.hInstance		= hInstance;
	wcex.hIcon			= LoadIcon(hInstance, MAKEINTRESOURCE(IDI_SOURCE));
	wcex.hCursor		= LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground	= (HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName	= MAKEINTRESOURCE(IDC_SOURCE);
	wcex.lpszClassName	= szWindowClass;
	wcex.hIconSm		= LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

	return RegisterClassEx(&wcex);
}
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   HWND hWnd;

   hInst = hInstance; // Store instance handle in our global variable

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}
LRESULT CALLBACK Dlg2Proc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
	
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;

	switch (msg)
		{
	 
	case WM_INITDIALOG:
		return TRUE;
		break;
	case WM_COMMAND:
		{
			switch(LOWORD(wParam))
			{		case IDC_BUTTON11:
					{
						EndDialog(hWnd,WM_CLOSE);
						DestroyWindow(hWnd);
						
					}break;
			}
			
		} break;
		
	case WM_PAINT:
		{
			hdc=BeginPaint(hWnd,&ps);
			Rectangle(hdc,50,250,100,50+(elapsedtimetango/1000));
			Rectangle(hdc,150,250,200,50+(elapsedtimebinar/1000));
			EndPaint(hWnd,&ps);
		} break;
	case WM_CLOSE:
		{
			EndDialog(hWnd,WM_CLOSE);
			DestroyWindow(hWnd);
		}break;
	}
	return FALSE;

}
LRESULT CALLBACK Dlg1Proc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
	
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;

	switch (msg)
		{
	 
	case WM_INITDIALOG:
		return TRUE;
		break;
	case WM_COMMAND:
		{
			switch(LOWORD(wParam))
			{		case IDC_BUTTON8:
					{
						EndDialog(hWnd,WM_CLOSE);
						DestroyWindow(hWnd);
						
					}break;
			}
			
		} break;
		
	case WM_PAINT:
		{
			hdc=BeginPaint(hWnd,&ps);
			Rectangle(hdc,50,150,100,50+(elapsedtimetango/100));
			Rectangle(hdc,150,150,200,50+(elapsedtimebinar/100));
			EndPaint(hWnd,&ps);
		} break;
	case WM_CLOSE:
		{
			EndDialog(hWnd,WM_CLOSE);
			DestroyWindow(hWnd);
		}break;
	}
	return FALSE;

}
LRESULT CALLBACK DlgProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{ 
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;

	switch (msg)
	{
	 
	case WM_INITDIALOG:
		return TRUE;
		break;
	case WM_COMMAND:
		{
			switch(LOWORD(wParam))
		{
			
			case IDC_BUTTON1:
				{ string[0]='\0';
				  
					for(int i=0;i<nr_nod-1;i++)
						{
							itoa(ok[i],s[i],10);
							strcat(string,s[i]);
							strcat(string,", ");
							
						}
					itoa(ok[nr_nod-1],s[nr_nod-1],10);
					strcat(string,s[nr_nod-1]);
					MessageBox(hWnd,
						string,
						"Valori noduri",
						MB_OK);	
				}
				break;
			case IDC_BUTTON2:
				{ int x1;
					GetDlgItemText ( hWnd , IDC_EDIT1 , buffer1 , 256 ); 
					 val=atoi(buffer1);	
					 x1=cautare(val);
					if(x1>0)
					{	
						MessageBox(hWnd,"Numarul a fost gasit in arborele tango!","INFO",MB_ICONINFORMATION);
					
					}
					else
					{	MessageBox(hWnd,"Numarul nu a fost gasit. \n Verificati lista valorilor. ","INFO",MB_ICONWARNING);
					EndDialog(hWnd,1);
					}

				}break;
				case IDC_BUTTON3:
				{
					int x2;
					GetDlgItemText ( hWnd , IDC_EDIT1 , buffer1 , 256 ); 
					 val=atoi(buffer1);			
					 x2=cautare2(val);
					
					if(x2>0)
					{	
						MessageBox(hWnd,"Numarul a fost gasit in arborele binar!","INFO",MB_ICONINFORMATION);
					
					}
					else
					{	MessageBox(hWnd,"Numarul nu a fost gasit. \n Verificati lista valorilor. ","INFO",MB_ICONWARNING);
					EndDialog(hWnd,1);
					}
				
				}break;
				case IDC_BUTTON4:
				{
					int x2;		
					StartCounter();
					for(int o=0;o<vec[0];o++)
					   x2=cautare2(mat[0][o]->value);
					elapsedtimebinar=GetCounter();

					int x1;
					StartCounter();
					for(int o=0;o<vec[0];o++)
						x1=cautare(mat[0][o]->value);
					 elapsedtimetango=GetCounter();
					
						char s[40];
						itoa(elapsedtimetango,s,10);
						MessageBox(hWnd,s,"TANGO",MB_OK);
						itoa(elapsedtimebinar,s,10);
						MessageBox(hWnd,s,"BINAR",MB_OK);
					if(elapsedtimetango<elapsedtimebinar)
					{	
						MessageBox(hWnd,"Cautarea valorilor din prima cale preferata a fost mai rapida\n in arborele TANGO ","INFO",MB_ICONINFORMATION);
					
					}
					else if(elapsedtimetango>elapsedtimebinar)
					{	MessageBox(hWnd,"Cautarea valorilor din prima cale preferata a fost mai rapida \nin arborele BINAR  ","INFO",MB_ICONWARNING);
					
					} 
					}break;
				case IDC_BUTTON5:
				{
					int x2;	
					StartCounter();
					for(int b=0;b<j;b++)
					    for(int k=0;k<vec[b];k++)
						    x2=cautare2(mat[b][k]->value);
					elapsedtimebinar=GetCounter();

					int x1;
					StartCounter();
					for (int b=0;b<j;b++)
					   for(int k=0;k<vec[b];k++)
					       x1=cautare(mat[b][k]->value);
					elapsedtimetango=GetCounter();
					char s[40];
					itoa(elapsedtimetango,s,10);
					MessageBox(hWnd,s," Timp TANGO",MB_OK);
					itoa(elapsedtimebinar,s,10);
					MessageBox(hWnd,s,"BINAR",MB_OK);	
					if(elapsedtimetango<elapsedtimebinar)
					{	
						MessageBox(hWnd,"Timpul mediu de cautare este mai mic in arborele \nTANGO ","INFO",MB_ICONINFORMATION);
					
					}
					else if(elapsedtimetango>elapsedtimebinar)
					{	MessageBox(hWnd," Timpul mediu de cautare este mai mic in arborele \n BINAR  ","INFO",MB_ICONWARNING);
				
					} 
					}break;
					
				case IDC_BUTTON6:
					{
						
						 string1[0]='\0';
						 
				  
					for(int z=0;z<vec[0]-1;z++)
						{
							itoa(mat[0][z]->value,cuv[z],10);
							strcat(string1,cuv[z]);
							strcat(string1,", ");
							
						}
					itoa(mat[0][vec[0]-1]->value,cuv[vec[0]-1],10);
					strcat(string1,cuv[vec[0]-1]);
					MessageBox(hWnd,
						string1,
						"Prima cale preferata",
						MB_OK);	
					} break;
				
				case IDC_BUTTON7:
					{
						int b=DialogBox(hInst, MAKEINTRESOURCE(IDD_DIALOG2),
						hWnd,reinterpret_cast<DLGPROC>(Dlg1Proc));

					}break;
					
				case IDC_BUTTON10:
					{
						int b=DialogBox(hInst, MAKEINTRESOURCE(IDD_DIALOG3),
						hWnd,reinterpret_cast<DLGPROC>(Dlg2Proc));

					}break;


				case IDC_BUTTONEXIT2:
					{
						EndDialog(hWnd,WM_CLOSE);
						DestroyWindow(hWnd);
					}break;
				case IDC_BUTTONEXIT:
					{
						exit(EXIT_SUCCESS);
					}break;
		}
			
		} break;
		
	case WM_CLOSE:
		{
			EndDialog(hWnd,WM_CLOSE);
			DestroyWindow(hWnd);
		}break;
	
	}
	return FALSE;
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;
	hWnd1=hWnd;
	switch (message)
	{
	case WM_CREATE:
		{hEdit=CreateWindowEx(WS_EX_CLIENTEDGE,
				"EDIT",
				"",
				WS_CHILD|WS_VISIBLE|
				ES_MULTILINE|ES_AUTOVSCROLL|ES_AUTOHSCROLL,
				50,
				130,
				200,
				100,
				hWnd,
				(HMENU)IDC_MAIN_EDIT,
				GetModuleHandle(NULL),
				NULL);
			HGDIOBJ hfDefault=GetStockObject(DEFAULT_GUI_FONT);
			SendMessage(hEdit,
				WM_SETFONT,
				(WPARAM)hfDefault,
				MAKELPARAM(FALSE,0));
			SendMessage(hEdit,
				WM_SETTEXT,
				NULL,
				NULL);

			// Create a push button
			HWND hWndButton=CreateWindowEx(NULL,
				"BUTTON",
				"OK",
				WS_TABSTOP|WS_VISIBLE|
				WS_CHILD|BS_DEFPUSHBUTTON,
				100,
				250,
				100,
				24,
				hWnd,
				(HMENU)IDC_MAIN_BUTTON,
				GetModuleHandle(NULL),
				NULL);
			SendMessage(hWndButton,
				WM_SETFONT,
				(WPARAM)hfDefault,
				MAKELPARAM(FALSE,0));
			// 
		}
		
		break;

	case WM_COMMAND:
			switch(LOWORD(wParam))
            {
				case IDC_MAIN_BUTTON:
				{
					
					SendMessage(hEdit,
						WM_GETTEXT,
						sizeof(buffer)/sizeof(buffer[0]),
						reinterpret_cast<LPARAM>(buffer));
					nr_nod=atoi(buffer);
					MessageBox(NULL,
						buffer,
						"Nr noduri:",
						MB_ICONINFORMATION);

			randomelemente();
			repetare_el(v,ok,nr_nod,l);
			sortare(ok,l);
			root=creare_nod(0,l,ok,0);
			 h=height(root);
			if(arbore_complet(root,h,nr_nod))
				{
					treeNode *pref[1000];
					int p;
					
					mat=(treeNode***)malloc(sizeof(treeNode**)*1000);
					for(int k=0;k<1000;k++)
						mat[k]=(treeNode**)malloc(sizeof(treeNode*)*1000);
					j=0;
					matrice_preordine(root,mat, pref, j, vec);
					treeNode *radacina;
					treeNode *roots[1000];
					linie(mat, vec,j, roots);
					TANGO_TREE(roots,j,mat);
					MessageBox(NULL,
						"Arborele ESTE complet",
						"INFO",
						MB_ICONINFORMATION);
					SetWindowText(GetDlgItem(hWnd,IDC_MAIN_EDIT)," ");
					int a=DialogBox(hInst, MAKEINTRESOURCE(IDD_DIALOG1),
						hWnd1,reinterpret_cast<DLGPROC>(DlgProc));
					
					break;
				}
			if(!arbore_complet(root,h,nr_nod))
				{
					MessageBox(NULL,
						"Arborele  NU ESTE complet. Incercati din nou !",
						"INFO",
						MB_ICONWARNING);
				exit(EXIT_SUCCESS);
					} 
				break;
			}

	}
			
			
		case WM_PAINT:
		
		{
			hdc = BeginPaint(hWnd, &ps);
HFONT font=CreateFont
(100,70,0,0,FW_NORMAL,FALSE,FALSE,FALSE,ANSI_CHARSET,OUT_DEFAULT_PRECIS,CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH|
FF_ROMAN,"ELEPHANT");
SetTextColor(hdc,(0,0,560));
TextOut(hdc,40,100,"Introduceti numarul de noduri: ",29);
font=CreateFont
(200,15,0,0,FW_NORMAL,FALSE,FALSE,FALSE,ANSI_CHARSET,OUT_DEFAULT_PRECIS,CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH|
FF_ROMAN,"ELEPHANT");
SetTextColor(hdc, RGB(0,20,640));
SelectObject(hdc,font);
TextOut(hdc,400,0,"TANGO TREE",10);
DeleteObject(font);
EndPaint(hWnd, &ps);
		}
		break;
		case WM_CLOSE:
			DestroyWindow(hWnd);
			break;
	case WM_DESTROY:
		PostQuitMessage(0);
		break;
	default:
		return DefWindowProc(hWnd, message, wParam, lParam);
	}
	return 0;
}


// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	UNREFERENCED_PARAMETER(lParam);
	switch (message)
	{
	case WM_INITDIALOG:
		return (INT_PTR)TRUE;

	case WM_COMMAND:
		if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
		{
			EndDialog(hDlg, LOWORD(wParam));
			return (INT_PTR)TRUE;
		}
		break;
	}
	return (INT_PTR)FALSE;
}
///////////////////////////////
void randomelemente()
{
	for(int i=0;i<nr_nod;i++)
		v[i]=rand();
}
void repetare_el(int *v, int *ok, int n, int &l)
{
	int p;
	l=1;
	ok[0]=v[0];
	for(int i=1;i<n;i++)
	{
		p=0;
		for(int j=0;j<i;j++)
		{
			if(v[i]!=v[j])
				p++;
		}
		
		if(p==i)
		{
			ok[l]=v[i];
			l++;
		}
	}

}
void sortare(int *ok, int n)
{
	int bla;
	do
	{
		bla=0;
		for(int i=0;i<n-1;i++)
			if(ok[i]>ok[i+1])
			{
				int aux=ok[i];
				ok[i]=ok[i+1];
				ok[i+1]=aux;
				bla=1;
			}
	}while(bla);
}
treeNode* creare_nod(int i, int j, int *v,treeNode *parent)
{
	if(i==j)
		return NULL;
	int mid=(i+j)/2;
	treeNode *nou=(treeNode*)malloc(sizeof(treeNode));
	nou->value=v[mid];
	nou->parent=parent;
	nou->l=NULL;
	nou->r=NULL;
	nou->ales=0;
	nou->color='r';
	nou->p=NULL;
	nou->left=creare_nod(i, mid, v,nou);
	nou->right=creare_nod(mid+1, j, v,nou);
	return nou;
}
int height(treeNode *subroot)
{
	if(subroot==NULL)
	{
		return 0;
	}
	if(subroot->left!=NULL || subroot->right!=NULL)
	{
		int hs=height(subroot->left);
		int hd=height(subroot->right);
		if(hs<hd)
			return hd+1;
		else
			return hs+1;
	}
	return 0;
}
int arbore_complet(treeNode *subroot, int h, int n)
{
	int count=1;
	for(int i=0;i<=h;i++)
		count=count*2;
	if(n==count-1)
		return 1;
	else
		return 0;
}
void calepreferata(treeNode *subroot, treeNode **pref, int &i)
{
	i=0;
	if(subroot==NULL)
		return;
	subroot->ales=1;
	pref[i]=subroot;
	i++;
	subroot=subroot->left;
	while(subroot)
	{
		if(subroot->value==subroot->parent->left->value)
		{
			subroot->ales=1;
			pref[i]=subroot;
			i++;
			subroot=subroot->right;
		}
		else
			if(subroot->value==subroot->parent->right->value)
		{
			subroot->ales=1;
			pref[i]=subroot;
			i++;
			subroot=subroot->left;
		}
	}
}
void matrice_preordine(treeNode *subroot, treeNode ***mat, treeNode **pref, int &j, int *vec)
{
	int i;
	if(subroot==NULL)
		return;
	if(subroot->ales==0)
	{
		calepreferata(subroot, pref, i);
		vec[j]=i;
		for(int k=0;k<i;k++)
		{
			mat[j][k]=(treeNode*)malloc(sizeof(treeNode));
			mat[j][k]=pref[k];
		}
		j++;
	}
	matrice_preordine(subroot->left, mat, pref, j, vec);
	matrice_preordine(subroot->right, mat, pref, j, vec);
}
void insert_case1(treeNode *&root_rb,treeNode *n)//recolorare in negru
{
	if(n->p==NULL)
		n->color='b';
	else 
		insert_case2(root_rb, n);
}
void insert_case2(treeNode*&root_rb,treeNode*n)//arbore ok
{
	if(n->p->color=='b')
		return;
	else
		insert_case3(root_rb, n);
}
void insert_case3(treeNode *&root_rb,treeNode *n)//parintele si unchiul sunt rosii; recolorare
{
	treeNode *u=uncle(n);
	treeNode *g;
	if((u!=NULL)&&(u->color=='r'))
	{
		n->p->color='b';
		u->color='b';
		g=grandparent(n);
		g->color='r';
		insert_case1(root_rb,n);
	}
	else
		insert_case4(root_rb, n);
}
void insert_case4(treeNode*&root_rb,treeNode *n)
{
	treeNode *g=grandparent(n);
	if((n==n->p->r)&&(n->p==g->l))
	{
		leftRotate(root_rb, n->p);
		n=n->l;
	}
	else
		if((n==n->p->l)&&(n->p==g->r))
		{
			rightRotate(root_rb, n->p);
			n=n->r;
		}
	insert_case5(root_rb,n);
}
void insert_case5(treeNode *&root_rb,treeNode *n)
{
	treeNode *g=grandparent(n);
	n->parent->color='b';
	g->color='r';
	if(n==n->p->l)
		rightRotate(root_rb,g);
	else
		leftRotate(root_rb,g);
}
void leftRotate(treeNode *&subroot,treeNode *x)
{
	treeNode *y;
	y = x->r;  //Set y
	x->r = y->l; // Turn y's left subtree into x's right subtree
	if( y->l != NULL)
		y->l->p = x; //Bridge the y's left sublink
	y->p = x->p; //Bridge x's old parent and y's parent
	if( x->p == NULL)
		subroot = y;
	else 
		if( x->value == x->p->l->value)
			 x->p->l = y; //Bridge x's old parent's left or right child
		else x->p->r = y;
	y->l = x; //put x on y's left
	x->p = y; //Take care of x's parent

return;
}
void rightRotate( treeNode *&subroot, treeNode *y){
 treeNode *x;
x = y->l; //set x
y->l = x->r; //Turn x's right subtree into y's left subtree
if ( x->r != NULL){
    x->r->p = y;
}
x->p= y->p; //Bridge y's old parent and x's parent
if( y->p == NULL){
    subroot = x;
} 
else if( y->value == y->p->l->value){
    y->p->l = x; //Bridge y's old parent's left or right child
}
else y->p->r = x;
x->r = y; //put y on x's right
y->p = x; //Take care of y's parent

return;

}
void rbInsert(treeNode *&subroot, treeNode *z){
treeNode *x = subroot;
treeNode *y;
if ( subroot == NULL ){
    subroot = z;
    subroot->color = 'b';
    return;
}
while ( x != NULL){
    y = x;
	if ( z->value < x->value){
        x = x->l;
    }
    else x = x->r;
}
z->p = y;
if ( y == NULL){
    subroot = z;
}
else if( z->value < y->value ){
    y->l = z;
}
else y->r = z;
//rbInsertFix(subroot,z);
insert_case1(subroot, z);
return;
}

void linie(treeNode ***mat, int *vec,int j, treeNode **roots)
{
	//radacinile arborilor rosu-negru
	for(int h=0;h<j;h++)
	{
		treeNode *subroot=NULL;
		for(int k=0;k<vec[h];k++)
			rbInsert(subroot, mat[h][k]);
		roots[h]=subroot;
		
	}
}

void TANGO_TREE(treeNode **roots, int j, treeNode ***mat)
{	
	rootinit=root;
	root=roots[0];
	for(int i=1;i<j;i++)
	{
		treeNode *aux=mat[i][0]->parent;
		if(roots[i]->value>aux->value)
		{
			while(aux->r!=NULL && roots[i]->value>aux->value)
				aux=aux->r;
			if(roots[i]->value<aux->value)
			{
				roots[i]->p=aux;
				aux->l=roots[i];
			}
			else
			{
				roots[i]->p=aux;
				aux->r=roots[i];
			}
		}
		else
		{
			while(aux->l!=NULL && roots[i]->value<aux->value)
				aux=aux->l;
			if(roots[i]->value<aux->value)
			{
				roots[i]->p=aux;
				aux->l=roots[i];
			}
			else
			{
				roots[i]->p=aux;
				aux->r=roots[i];
			}
		}
	}
}

int cautare(int val)
{
	treeNode *p=root;
	while(p!=NULL)
	{
		if(val==p->value)
			return 1;
		if(val<p->value)
			p=p->l;
		else
			p=p->r;
	}
	return 0;
}
int cautare2(int val)
{
	treeNode *p=rootinit;
	while(p!=NULL)
	{
		if(val==p->value)
			return 1;
		if(val<p->value)
			p=p->left;
		else
			p=p->right;
	}
	return 0;
}




